package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Description 删除并获得点数
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.5
 */

public class T740 {
    public static void main(String[] args) {
//        int[] nums = new int[]{3,4,2};
        int[] nums = new int[]{2, 2, 3, 3, 3, 4};
        T740 t740 = new T740();
        System.out.println(t740.deleteAndEarn(nums));
    }

    //dp[i] = Math.max(dp[i - 1], dp[i - 2] +  all[i]);
    //首先，我们先明确一个概念，就是每个位置上的数字是可以在两种前结果之上进行选择的：
    //如果你不删除当前位置的数字，那么你得到就是前一个数字的位置的最优结果。
    //如果你觉得当前的位置数字i需要被删，那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。
    public int deleteAndEarn(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] all = new int[max + 1];
        for (int i = 0; i < nums.length; i++) {
            all[nums[i]] += nums[i];
        }
        System.out.println(all);

        int[] dp = new int[max + 1];
        dp[0] = 0;
        dp[1] = all[1];
        for (int i = 2; i < max + 1; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] +  all[i]);
        }

        return dp[max];
    }


    //下面纯暴力揭发不行，因为按照顺序进行暴力，并不是最贪心的策略
    public int deleteAndEarn1(int[] nums) {
        int result = -1;
        for (int i = 0; i < nums.length; i++) {
            new ArrayList(nums.length);
            List<Integer> datas = Arrays.stream(nums).boxed().collect(Collectors.toList());
            int tmp = chooseAndDel(datas, i);
            if (tmp > result) {
                result = tmp;
            }
        }
        return result;
    }

    public int chooseAndDel(List<Integer> list, int startIndex) {
        int result = 0;
        for (int i = startIndex; ; i++) {
            if (i == list.size()) {
                i = 0;
            }

            if (list.get(i) == -1) {
                if (i == startIndex) {
                    break;
                }
                continue;
            }
            Integer chooseNum = list.get(i);
            result += chooseNum;
            list.set(i, -1);

            for (int j = 0; j < list.size(); j++) {
                if (list.get(j) == chooseNum - 1
                        || list.get(j) == chooseNum + 1) {
                    list.set(j, -1);
                }
            }

        }
        return result;

    }


}
